436. Find Right Interval
Medium

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

 

Example 1:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

 

Constraints:

  • 1 <= intervals.length <= 2 * 104
  • intervals[i].length == 2
  • -106 <= starti <= endi <= 106
  • The start point of each interval is unique.
Accepted
64,848
Submissions
133,199
Seen this question in a real interview before?
Related Topics

Average Rating: 4.00 (22 votes)

Premium

Solution


Approach 1: Brute Force

The simplest solution consists of picking up every interval in the set and looking for the the interval whose start point is larger(by a minimum difference) than the chosen interval's end point by scanning the complete set for every interval chosen. While scanning, we keep a track of the interval with the minimum start point satisfying the given criteria along with its index. The result obtained for every interval chosen is stored at the corresponding index in the res array which is returned at the end.

Complexity Analysis

  • Time complexity : O(n2)\mathcal{O}(n^2). The complete set of nn intervals is scanned for every(nn) interval chosen.

  • Space complexity : O(n)\mathcal{O}(n). res\text{res} array of size nn is used.


Approach 2: Using Sorting + Scanning

We make use of a hashmap hash\text{hash}, which stores the data in the form of a (Key, Value)\text{(Key, Value)} pair. Here, the Key\text{Key} corresponds to the interval chosen and the Value\text{Value} corresponds to the index of the particular interval in the given intervals\text{intervals} array. We store every element of the intervals\text{intervals} array in the hashhash-map.

Now, we sort the intervals\text{intervals} array based on the starting points. We needed to store the indices of the array in the hashmap, so as to be able to obtain the indices even after the sorting.

Now, we pick up every interval of the sorted array, and find out the interval from the remaining ones whose start point comes just after the end point of the interval chosen. How do we proceed? Say, we've picked up the ithi^{th} interval right now. In order to find an interval satisfying the given criteria, we need not search in the intervals behind it. This is because the intervals\text{intervals} array has been sorted based on the starting points and the end point is always greater than the starting point for a given interval. Thus, we search in the intervals only with indices jj, such that i+1<j<ni+1< j < n. The first element encountered while scanning in the ascending order is the required result for the interval chosen, since all the intervals lying after this interval will have comparatively larger start points.

Then, we can obtain the index corresponding to the corresponding interval from the hashmap, which is stored in the corresponding entry of the resres array. If no interval satisfies the criteria, we put a -1\text{-1} in the corresponding entry.

Complexity Analysis

  • Time complexity : O(n2)O(n^2).

    • Sorting takes O(nlogn)O\big(n\log{n}\big) time.
    • For the first interval we need to search among n1n-1 elements.
    • For the second interval, the search is done among n2n-2 elements and so on leading to a total of: (n1)+(n2)+...+1=n.(n1)2=O(n2)(n-1) + (n-2) + ... + 1 = \frac{n.(n-1)}{2} = O(n^2) calculations.
  • Space complexity : O(n)O(n). res\text{res} array of size nn is used. A hashmap hash\text{hash} of size nn is used.


We can optimize the above approach to some extent, since we can make use of the factor of the intervals\text{intervals} array being sorted. Instead of searching for the required interval in a linear manner, we can make use of Binary Search to find an interval whose start point is just larger than the end point of the current interval.

Again, if such an interval is found, we obtain its index from the hashmap and store the result in the appropriate res\text{res} entry. If not, we put a -1\text{-1} at the corresponding entry.

Complexity Analysis

  • Time complexity : O(nlogn)O\big(n\log{n}\big). Sorting takes O(nlogn)O\big(n\log{n}\big) time. Binary search takes O(logn)O\big(\log{n}\big) time for each of the nn intervals.

  • Space complexity : O(n)O(n). res\text{res} array of size nn is used. A hashmap hash\text{hash} of size O(n)O(n) is used.


Approach 4: Using TreeMap

In this approach, instead of using a hashmap, we make use of a TreeMap starts\text{starts}, which is simply a Red-Black Tree(a kind of balanced Binary Search Tree) . This Treemap start\text{start} stores data in the form of (Key, Value)\text{(Key, Value)} pair and always remain sorted based on its keys. In our case, we store the data such that the start point of an interval acts as the Key\text{Key} and the index corresponding to the interval acts as the value, since we are concerned with data sorted based on the start points, as discussed in previous approaches. Every element of the intervals\text{intervals} array is stored in the TreeMap.

Now, we choose each element of the intervals\text{intervals} array and make use of a function TreeMap.ceilingEntry(end_point) to obtain the element in the TreeMap with its Key\text{Key} just larger than the end_point\text{end\_point} of the currently chosen interval. The function ceilingEntry(Key) returns the element just with its Key\text{Key} larger than the Key(passed as the argument) from amongst the elements of the TreeMap and returns null if no such element exists.

If non-null value is returned, we obtain the Value\text{Value} from the (Key, Value)\text{(Key, Value)} pair obtained at the appropriate entry in the res\text{res} array. If a null value is returned, we simply store a -1\text{-1} at the corresponding res\text{res} entry.

Complexity Analysis

  • Time complexity : O(NlogN)O\big(N \cdot \log{N}\big). Inserting an element into TreeMap takes O(logN)O\big(\log{N}\big) time. NN such insertions are done. The search in TreeMap using ceilingEntry also takes O(logN)O\big(\log{N}\big) time. NN such searches are done.

  • Space complexity : O(N)O(N). res\text{res} array of size nn is used. TreeMap starts\text{starts} of size O(N)O(N) is used.


Algorithm

The intuition behind this approach is as follows: If we maintain two arrays,

  1. intervals\text{intervals}, which is sorted based on the start points.

  2. endIntervals\text{endIntervals}, which is sorted based on the end points.

Once we pick up the first interval(or, say the ithi^{th} interval) from the endIntervals\text{endIntervals} array, we can determine the appropriate interval satisfying the right interval criteria by scanning the intervals in intervals\text{intervals} array from left towards the right, since the intervals\text{intervals} array is sorted based on the start points. Say, the index of the element chosen from the intervals\text{intervals} array happens to be jj.

Now, when we pick up the next interval(say the (i+1)th(i+1)^{th} interval) from the endIntervals\text{endIntervals} array, we need not start scanning the intervals\text{intervals} array from the first index. Rather, we can start off directly from the jthj^{th} index where we left off last time in the intervals\text{intervals} array. This is because end point corresponding to endIntervals[i+1]\text{endIntervals[i+1]} is larger than the one corresponding to endIntervals[i]\text{endIntervals[i]} and none of the intervals from intervals[k]\text{intervals[k]}, such that 0<k<j0< k < j, satisfies the right neighbor criteria with endIntervals[i]\text{endIntervals[i]}, and hence not with endIntervals[i+1]\text{endIntervals[i+1]} as well.

If at any moment, we reach the end of the array i.e. j=intervals.lengthj=\text{intervals.length} and no element satisfying the right interval criteria is available in the intervals\text{intervals} array, we put a -1\text{-1} in the corresponding res\text{res} entry. The same holds for all the remaining elements of the endIntervals\text{endIntervals} array, whose end points are even larger than the previous interval encountered.

Also we make use of a hashmap hash\text{hash} initially to preserve the indices corresponding to the intervals even after sorting.

For more understanding see the below animation:

Current
1 / 16

Complexity Analysis

  • Time complexity : O(NlogN)O\big(N \cdot \log{N}\big). Sorting takes O(NlogN)O\big(N \cdot \log{N}\big) time. A total of O(N)O(N) time is spent on searching for the appropriate intervals, since the endIntervals\text{endIntervals} and intervals\text{intervals} array is scanned only once.

  • Space complexity : O(N)O(N). endIntervals\text{endIntervals}, intervals\text{intervals} and res\text{res} array of size NN are used. A hashmap hash\text{hash} of size O(N)O(N) is used.

Report Article Issue

Comments: 12
lenchen1112's avatar
Read More

Why there is no heap approach?
O(NlogN) time and O(N) space as well.

import heapq
class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        heap, result = [], [-1] * len(intervals)
        for idx, interval in sorted(enumerate(intervals), key=lambda enum: enum[1]):
            while heap and heap[0][0] <= interval[0]:
                _, i = heapq.heappop(heap)
                result[i] = idx
            heapq.heappush(heap, (interval[1], idx))
        return result

6
Show 2 replies
Reply
Share
Report
miner_liang's avatar
Read More

Approach #4 is not readable?

5
Show 1 reply
Reply
Share
Report
azimbabu's avatar
Read More

The sorting + scanning approach's implementation does not match the description as the scanning does not stop at the first element found. In fact, by doing that I got that accepted without TLE.

4
Reply
Share
Report
thetopdog's avatar
Read More

This can also be solved using a 2 heap approach in O(NlogN) time. I'v added the comments in line with the code to make it understandable.
Here is the C++ code :

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        priority_queue<pair<int,int>> endTimeMaxHeap;
        priority_queue<pair<int,int>> startTimeMaxHeap;
        vector<int>result(intervals.size());
        //Create the max heap for both start and end times of the form <start,idx> and <end,idx>
        for(int i = 0; i < intervals.size(); i++){
            startTimeMaxHeap.push(make_pair(intervals[i][0], i));
            endTimeMaxHeap.push(make_pair(intervals[i][1], i));
        }
        for(int i = 0; i < intervals.size(); i++){
            //Add default answer first
            result[endTimeMaxHeap.top().second] = -1;
            //Check of we have a start entry that is greater than the current max end time
            if(startTimeMaxHeap.top().first >= endTimeMaxHeap.top().first){
                //Initialize the max start time element and pop it
                auto startTop = startTimeMaxHeap.top();
                startTimeMaxHeap.pop();
                //Find the min start time entry that will satisfy the current max end time as the next interval.
                //Discard all larger start time entries
                while(!startTimeMaxHeap.empty() && startTimeMaxHeap.top().first >= endTimeMaxHeap.top().first){
                    startTop = startTimeMaxHeap.top();
                    startTimeMaxHeap.pop();
                }
                //Add the actual next interval since we found it
                result[endTimeMaxHeap.top().second] = startTop.second;
                //Re-add the top of start time max since it could be the next of an earlier end time
                startTimeMaxHeap.push(startTop);
            }
            //Clear the end time entry since we processed it
            endTimeMaxHeap.pop();
        }
        return result;
    }
};

1
Reply
Share
Report
practicerunnn's avatar
Read More

TreeMap/Heap are better than sorting based approaches only when the data is dynamic (with insertions/deletions). If the data is static, there is no reason to use these dynamic data structures instead of sorting.

1
Show 2 replies
Reply
Share
Report
133c7's avatar
Read More

There is a typo in approach 2.

In order to find an interval satisfying the given criteria, we need not search in the intervals behind it.

We need to search precisely the intervals behind it, because the intervals are sorted by the starting points.

1
Reply
Share
Report
rajatag03's avatar
Read More

Can anyone help why the last example shows interval with same start point for two interval when the question clearly mentions otherwise?

0
Reply
Share
Report
klimkina's avatar
Read More

#4
q = [(intervals[i][0], i) for i in range(len(intervals))]
q.append((float('inf'), -1)) #centry
q.sort()
return [q[bisect.bisect_left(q, (r,-1))][1] for l, r in intervals]

0
Reply
Share
Report
jca88's avatar
Read More

good solution progression slowly building up the optimal!

0
Reply
Share
Report
dougkenyon34's avatar
Read More

I use TreeMap all the time and today I am just learning about the ceilingXXX methods.

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
08/28/2020 09:40Accepted180 ms30.7 MBcpp
08/28/2020 09:39Accepted196 ms32.9 MBcpp
08/28/2020 09:37Wrong AnswerN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.